1. Field of the Invention
The present invention relates to an image matching device and method for motion pictures which are suitable for the case of performing a motion-compensated TV standards conversion, a video encoding or a depth extraction processing from stereo videos (a set of stationary images or videos formed of a left eye image and a right eye image) and which automatically estimate motion in an videos or automatically detect corresponding points between stereo videos formed of a left eye and right eye images.
2. Description of the Related Art
Conventional examples of systems usually used in an image matching processing for automatically estimating motion in videos or automatically detecting corresponding points between stereo videos formed of a left eye and right eye images as in a television broadcasting and a visual telephone include a block matching method and an iterative gradient method. As one of documents to explain such methods, there is “Improvement in motion-compensated TV standards conversion” (Kawada et. al, The journal of the institute of image information and television engineers, Vol. 51, No. 9 (1997), pp. 1577 to 1586).
In the case of the motion estimation, a video is basically divided into a large number of small blocks. Then, a current frame is compared to a previous frame for each of the blocks to calculate motion. In the case of the stereo matching, “the current frame” and “the previous frame” may be substituted with “a left eye image” and “a right eye image”, respectively. Thus, the invention of the present application will mainly describe the case of the motion estimation and a detailed description of the case of the stereo matching will be omitted.
According to the aforementioned image matching processing, the case in which a correct matching can be performed and the case in which the correct matching cannot be performed occur depending on a pattern or design of an input video. In the case of the iterative gradient method, for example, the following description can be given.
A motion vector v (for each block within a video) which is calculated by the iterative gradient method can be calculated by the following expression (1) with an initial displacement motion vector being indicated by v0 (see the aforementioned publication).V=ΔV+V0  (1)
wherein the horizontal and vertical components Δvx and Δvy of a differential vector Δv can be expressed by the following expressions (2) and (3) by using horizontal and vertical gradients Δx, Δy of a pixel value and a difference Δt between motion-compensated fields (or frames) by the initial displacement motion vector v0. The sum may be applied to all pixels within the corresponding block.
                              Δ          ⁢                                          ⁢                      v            x                          =                                                                                                                        (                                              ∑                                                                                                  ⁢                                                  Δ                          ⁢                                                                                                          ⁢                          x                          ⁢                                                                                                          ⁢                          Δ                          ⁢                                                                                                          ⁢                          y                                                                    )                                        ⁢                                          (                                              ∑                                                                                                  ⁢                                                  Δ                          ⁢                                                                                                          ⁢                          t                          ⁢                                                                                                          ⁢                          Δ                          ⁢                                                                                                          ⁢                          y                                                                    )                                                        -                                                                                                                          (                                          ∑                                                                                          ⁢                                              Δ                        ⁢                                                                                                  ⁢                                                  y                          2                                                                                      )                                    ⁢                                      (                                          ∑                                                                                          ⁢                                              Δ                        ⁢                                                                                                  ⁢                        t                        ⁢                                                                                                  ⁢                        Δ                        ⁢                                                                                                  ⁢                        x                                                              )                                                                                                          ∑                                                          ⁢                              Δ                ⁢                                                                  ⁢                                  x                  2                                ⁢                                  ∑                                                                          ⁢                                      Δ                    ⁢                                                                                  ⁢                                          y                      2                                                                                            -                                          (                                  ∑                                                                          ⁢                                      Δ                    ⁢                                                                                  ⁢                    x                    ⁢                                                                                  ⁢                    Δ                    ⁢                                                                                  ⁢                    y                                                  )                            2                                                          (        2        )                                          Δ          ⁢                                          ⁢                      v            y                          =                                                                                                                        (                                              ∑                                                                                                  ⁢                                                  Δ                          ⁢                                                                                                          ⁢                          x                          ⁢                                                                                                          ⁢                          Δ                          ⁢                                                                                                          ⁢                          y                                                                    )                                        ⁢                                          (                                              ∑                                                                                                  ⁢                                                  Δ                          ⁢                                                                                                          ⁢                          t                          ⁢                                                                                                          ⁢                          Δ                          ⁢                                                                                                          ⁢                          x                                                                    )                                                        -                                                                                                                          (                                          ∑                                                                                          ⁢                                              Δ                        ⁢                                                                                                  ⁢                                                  x                          2                                                                                      )                                    ⁢                                      (                                          ∑                                                                                          ⁢                                              Δ                        ⁢                                                                                                  ⁢                        t                        ⁢                                                                                                  ⁢                        Δ                        ⁢                                                                                                  ⁢                        y                                                              )                                                                                                          ∑                                                          ⁢                              Δ                ⁢                                                                  ⁢                                  x                  2                                ⁢                                  ∑                                                                          ⁢                                      Δ                    ⁢                                                                                  ⁢                                          y                      2                                                                                            -                                          (                                  ∑                                                                          ⁢                                      Δ                    ⁢                                                                                  ⁢                    x                    ⁢                                                                                  ⁢                    Δ                    ⁢                                                                                  ⁢                    y                                                  )                            2                                                          (        3        )            
The initial displacement motion vector v0 is determined by a matching with already calculated motion vectors of neighbor blocks being candidates (see the aforementioned publication).
In expressions (2) and (3), especially when denominators are small, calculations similar to a division by 0 are performed. Thus, large errors may be generated even by small disturbance factors such as noises.
Especially when a regularly repeated pattern exists in the pattern or design, problems may be presented. In such case, image matching can be found in a large number of motion vectors. Thus, motion vectors that are different from actual motions are calculated due to noises or the like, so that an interpolated video may be extremely degraded when performing the TV standards conversion.
On the other hand, in accordance with the iterative gradient method, motions are calculated iteratively by using gradients of image surfaces. Thus, if correlation between frames is small, motions are hardly calculated. From this point of view, scenes shot by a high speed shutter especially present problems. Because motion objects are set apart between videos which are adjacent with each other in view of time, motions tend to be hardly captured.
As described above, there exists a video which becomes problematic when Δv becomes large and a video which becomes problematic when Δv becomes small such as a video in which a regularly repeated pattern exists in a design and a video with small correlation between frames. Accordingly, there arises a problem in that if a matching processing for the former image is performed successfully, a matching processing for the latter image is not performed successfully, and vice versa.
In addition, according to a conventional block-based matching processing, when different motions exist within the corresponding block, for example, when the boundary between a motion image and a background image exists within a block, a correct motion vector cannot be calculated.